Communication in a computer internetwork involves the exchange of data between two or more entities interconnected by communication media configured as local area networks (LANs) and wide area networks (WANs). The entities are typically software programs executing on hardware computer platforms, such as end stations and intermediate stations. In particular, communication software executing on the end stations correlate and manage data communication with other end stations. The stations typically communicate by exchanging discrete packets or frames of data according to predefined protocols. A protocol, in this context, consists of a set of rules defining how the stations interact with each other. For example, a LAN employs a data communication protocol (LAN standard), such as Token Ring, Ethernet or Token Bus, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack).
To form a WAN, one or more intermediate devices are often used to interconnect multiple LANs. A bridge is an example of an intermediate station that may be used to provide a xe2x80x9cbridgingxe2x80x9d function between two or more LANs to form a relatively small domain of stations, such as a subnetwork. Subnetworks or subnets provide an organizational overlay to an internetwork that facilitates transmission of data between the end stations. A switch may be utilized to provide a xe2x80x9cswitchingxe2x80x9d function for transferring information, such as data frames, between LANs. Typically, the switch is a computer having a plurality of ports that couple the switch to several LANs and to other switches. The switching function includes receiving data frames at an inbound port and transferring them to at least one outbound port of the switch. A router is an intermediate station that interconnects subnets and executes network routing software to allow expansion of communication to end stations of other subnets. Collectively, these hardware and software components comprise a communications internetwork.
FIG. 1 is a schematic block diagram of a conventional Token Ring (TR) internetwork 100 comprising a plurality of TR LANs interconnected by conventional bridges and a router (R). Each token ring is assigned a ring number (RN), such as RN001, RN222 and RN123, and each bridge is assigned a bridge number (BN), such as BN1-3. The RNs assigned to the token rings must be unique within each bridged TR subnetwork that extends to the router. That is, RNs assigned to the token rings within each subnetwork must be different, although BNs assigned to the bridges within each subnetwork may be similar. An exception to this latter rule involves the use of redundant bridges coupling common TR LANs; here, the redundant bridges must have unique BNs in order to distinguish one another.
In the TR internetwork, there may be multiple paths between a source end station and a destination end station. To send a TR frame from a source (such as Station A) to a destination (such as Station B) along a particular path of the internetwork, the source may insert information within a routing information field (RIF) of the frame that specifies the particular path to the destination. FIG. 2 is a schematic diagram of a portion of a conventional TR frame 200 comprising destination address (DA) and source address (SA) medium access control (MAC) fields 202-204 and a RIF header 210. The RIF header 210, in turn, comprises a type (TYPE) field 212, a RIF length indicator (LENGTH) field 214, a direction bit (DIRECTION) field 216 and a ROUTE field 220 that may include a plurality of RN/BN pairs needed to describe the path. Each RN/BN pair comprises 2 bytes, wherein the RN is 12 bits and the BN is 4 bits. The RIF header 210 terminates with a 4-bit padding (PAD) field 228 of zeros.
The source typically acquires the information for insertion into the RIF through the issuance of a special TR frame called an All Routes Explorer (ARE) frame that is broadcasted throughout the TR subnetwork. An ARE frame is typically used to find all paths to a particular destination; an example of a frame used to strictly find the destination is a Spanning Tree Explorer (STE) frame. The STE frame only propagates over network segments that are along a defined spanning tree path to the destination; consequently, the destination only receives one copy of the frame. Execution of a spanning tree algorithm within the bridges results in blocking of certain ports to obviate propagation of frames around loops.
Source Route Bridging (SRB) describes a bridging technique that forwards TR frames based on the RIF information stored in the frame; an example of a frame that has a RIF is called a Specifically Routed Frame (SRF). In contrast, Transparent Bridging (TB) is a bridging technique that forwards TR frames based on their MAC addresses using a forwarding table. Source Route Transparent (SRT) bridging is a merging of the SRB and TB techniques; that is, if there is a RIF in the frame transported over an SRT bridge network, forwarding decisions are based on that RIF, whereas if there is no RIF in the frame, forwarding decisions are made based on the MAC address of the frame using the forwarding table. A TR frame that does not have a RIF is called a Non-Source Route (NSR) frame.
When issuing an ARE frame, the source (Stn A) initially sets the RIF length 214 to xe2x80x9c2xe2x80x9d (the length of the header 210) signifying that there is no information contained in the route field 220 of the RIF, and loads the type field 212 of the header with information specifying the type of frame, e.g., an ARE frame. Stn A then transmits the ARE frame over token ring RN001 where it is received by each station, including each bridge, connected to the token ring. Upon receiving the frame, each bridge inserts information into the RIF prior to forwarding a copy of the ARE frame onto its connected token ring.
In general, each bridge inserts into the RIF (i) its bridge number and (ii) the ring number of the token ring to which it is forwarding the frame; however, when a bridge receives an ARE frame having a RIF length of xe2x80x9c2xe2x80x9d, the bridge also inserts into the RIF the ring number of the token ring from which the frame is received. For example, a first BN1 inserts into the RIF the following information: the RN of the token ring from which the frame is received, its BN and the RN of the ring to which it is forwarding the frame  less than 001.1.123 greater than . The contents of the RIF thus describe the path followed by the ARE frame to reach token ring RN123.
The RIF contents for other copies of the ARE frame broadcasted throughout the TR subnetwork include (i) RIF= less than 001.1.222 greater than and (ii) RIF= less than 001.2.222 greater than . These copies of the ARE frame are forwarded over RN222 and the bridges connected to the ring update the RIF of the ARE frames prior to forwarding them to their connected LANs. For example when bridge BN3 forwards the ARE frame to RN123, it updates the RIF header 210, including the length field 214, as a result of inserting its bridge number and connected ring number into the RIF. Thus, the contents of the RIF of an ARE frame propagating over RN123 are  less than 001.1.222.3.123 greater than . Destination (Stn B) receives three ARE frames, one of which has a RIF with contents  less than 001.1.123 greater than , another having RIF contents  less than 001.1.222.3.123 greater than and a third having RIF contents of  less than 001.2.222.3.123 greater than .
Stn B chooses one of the ARE frames (and its RIF contents) as the route over which it returns a response frame; typically, the destination chooses the frame it received first, which may be the frame having the shortest RIF to the source. Stn B thus returns a SRF frame to the source over a path  less than 001.1.123 greater than specified in the RIF. The frame type is indicated as a SRF frame and the direction bit is altered to enable interpretation of the contents of the RIF. In the case of a response frame, the direction bit is inverted to denote that the RIF contents are interpreted in a reverse direction to describe the path to the source.
In general, a properly functioning bridge does not forward a copy of a STE frame or an ARE frame back over a token ring from which it has already traversed. When the ARE frame is xe2x80x9cfloodedxe2x80x9d over RN001, one copy of the frame is received by bridge BN2 and forwarded to RN222, while another copy of the frame is received at a second BN1 and forwarded to RN222. Because each of these bridges reside on the same token ring, the copy of the frame forwarded over RN222 from BN2 is received by BN1 and, similarly, the copy of the frame forwarded over RN222 by BN1 is received by BN2. Yet, those bridges do not forward copies of the frames back onto RN001 because the ARE frames previously traversed that ring. Specifically, BN1 examines the contents of the RIF and, upon detecting that the ARE frame had previously traversed RN001, blocks its port to that token ring. Blocking of the port effectively discards the frame and prevents it from circulating endlessly around a loop, while also preventing end stations from receiving multiple copies of the frame.
A token ring network is typically implemented through the use of TR concentrators (or xe2x80x9chubsxe2x80x9d) interconnected in a xe2x80x9cdaisy chainxe2x80x9d manner, wherein each concentrator is coupled to end stations via point-to-point wire cables 310. FIG. 3 is a schematic diagram of a conventional TR concentrator network arrangement 300. Collectively, the interconnected concentrators 302-308 form a physical loop/ring configuration that starts at a first TR concentrator 302 and continues through each end station coupled to the concentrator; this configuration extends to each connected TR concentrator up to a last concentrator 308, where it xe2x80x9cloops-backxe2x80x9d to the first concentrator. Access to the ring is determined in accordance with a token message that propagates among all of the end stations coupled to the ring. A problem with this conventional network arrangement involves the limited bandwidth available to each station over the cables 310; for example, all stations coupled to the physical token ring share 16 megabits per second (Mbps) of bandwidth. In contrast, intermediate stations (switches) in an Ethernet environment are interconnected by 100 Mbps xe2x80x9cpipesxe2x80x9d that increase the bandwidth available per station.
One way to achieve additional bandwidth in a token ring environment is to apportion the token ring into smaller subrings, each of which is coupled to a bridge. Yet, apportioning a token ring network into subrings requires careful consideration because of the limitations associated with token ring networks. Since each ring number comprises 12 bits, there is only a finite number of ring numbers available per subnet. The total length of the RIF of a TR frame is less than or equal to 30 bytes, thus limiting the RIF to a total of fourteen (14) RN/BN pairs for the typical TR frame 200. Moreover, subrings do not generally scale well for modern networking environments wherein each server coupled to the network requires its own TR concentrator to achieve necessary bandwidth requirements.
Another approach to increasing bandwidth in a token ring environment involves the use of intermediate stations that are compatible with the Dedicated Token Ring (DTR) bridge standard promulgated by the Institute of Electrical and Electronics Engineers (IEEE) in Annex K to the IEEE 802.5 standard (hereinafter xe2x80x9cAnnex Kxe2x80x9d), which governs token ring LANs. Annex K defines a 2-tier switching model for a single LAN switch containing a Bridge Relay Function (BRF) to bridge between ports of different ring numbers and a Concentrator Relay Function (CRF) to switch between ports of the same ring number.
FIG. 4 is a schematic diagram of a switch 400 containing a plurality of CRFs (CRF111-333) coupled to a BRF1 to provide bridging and switching operations among physical token ring (TR) media/segments coupled to the switch. Each CRF has a plurality of ports that interconnect a plurality of TR segments into one logical token ring having a single ring number. This arrangement is advantageous because it increases the total available bandwidth per logical token ring. That is, for a 4-port switch arrangement, a total of 64 Mbps of bandwidth is available for, e.g., CRF111.
Functionally, the CRF xe2x80x9cswitchesxe2x80x9d TR frames from one TR segment to another, while the BRF xe2x80x9cbridgesxe2x80x9d those frames between different CRFs. That is, rather than or in addition to forwarding frames from one TR segment to another, CRF111 may pass them to its associated BRF1 which may, in turn, forward the frames to CRF222. CRF222 may then forward the frames over one of its TR segments. Thus, the 2-tier switching model allows BRF1 to transfer TR frames between different logical token ring numbers.
FIG. 5 is a schematic block diagram of a conventional bridging arrangement 500 comprising a plurality of switches SW1xe2x88x9d2 with a plurality of BRFs (BRF1-3), each of which is coupled to a plurality of CRFs. In general, coupling of a BRF to the CRFs forms a subnetwork; multiple subnetworks may then be interconnected by a router (R) located internal (or external) to a switch. However, a CRF may be extended from one physical location to another using a wire 510 that connects one port of the CRF in a switch to another port of the CRF in another switch.
For example, CRF222 may be defined in each switch SW1-2 and its function logically extended between the switches by coupling two ports through the wire 510. Although this enables its ports to occupy a single logical ring number, CRF222 is logically coupled between two different BRFs (BRF1 and BRF2). Each BRF in the switches has an assigned bridge number and constitutes a bridge hop. Notably, the wire 510 used to couple the CRF ports of the switches SW1-2 is generally similar to the cable 310 coupling stations/concentrators of a token ring and, thus, supports 16 Mbps of bandwidth.
In addition to subnets, a computer internetwork may be segregated into a series of network groups. For example, U.S. Pat. No. 5,394,402, to Ross (the xe2x80x9c""402 Patentxe2x80x9d) discloses an arrangement that is capable of associating any port of a switch with any particular segregated network group. According to the ""402 Patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. Ross discloses a system that associates VLAN designations with at least one internal switch port and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned. Thus, those entities having the same VLAN designation function as if they are all part of the same LAN.
The VLAN designation for each internal port is stored in a memory portion of the switch such that every time a message is received by the switch on an internal port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in a memory based on the internal port where the message originated. Message exchanges between parts of the network having different VLAN designations are specifically prevented in order to preserve the boundaries of each VLAN segment. In addition to the ""402 patent, the Institute of Electrical and Electronics Engineers (IEEE) is preparing a standard for Virtual Bridged Local Area Networks. See IEEE Standard 802.1q (draft).
U.S. Pat. No. 5,742,604, titled Interswitch Link Mechanism for Connecting High-Performance Network Switches, by Edsall et al. (the xe2x80x9c""604 patentxe2x80x9d) discloses an inter-switch link (ISL) encapsulation mechanism for efficiently transporting packets or frames, including VLAN-modified frames, between switches while maintaining the VLAN association of the frames. This patent, which is commonly owned with the present application, discloses an ISL link that connects ISL interface circuitry disposed at two switches. The transmitting ISL circuitry encapsulates the frame being transported within an ISL header and ISL error detection information, while the ISL receiving circuitry strips off this information and recovers the original frame.
FIG. 6 is a block diagram of an ISL encapsulated frame 600. The encapsulated frame 600 includes an original frame, such as Ethernet frame 602, that is encapsulated within an ISL header 604 including an ISL CRC field 606. The Ethernet frame 602 includes a plurality of well-known fields, such as a Medium Access Control (MAC) destination address (DA) 608, a MAC source address (SA) 610, a data field 612 and an Ethernet frame check sequence (FCS) field 614, among others. The ISL header 604 comprises a plurality of fields including an ISL DA field 616, a type field 618, an ISL SA field 620, a length (LEN) field 622 and a VLAN identifier (ID) field 624.
The ISL DA field 616 identifies the ISL interface circuitry of the receiving switch and may be a multicast or unicast address. The type field 618 indicates the type of original frame that is encapsulated. The ISL SA field 620 may identify the ISL interface circuitry forwarding the frame 600 and the length field 622 indicates the length of frame 600. The VLAN ID field 624 carries the VLAN designation associated with the original frame 602 being encapsulated. To the extent the original frame 602 includes its own VLAN ID field, such as a Tag Protocol Identifier Field (TPID) field as specified in the IEEE 802.1q draft standard, this designation may be repeated in field 624. In addition, the ISL encapsulated frame 600 includes an ISL FCS field 606 that is loaded with error detection values (such as cyclic redundancy checks) by the transmitting switch prior to forwarding the frame 600 over the ISL link.
As noted, an example of the original frame format encapsulated by the ISL header 604 is an Ethernet frame 602. Prior attempts to transport token ring (TR) frames over an ISL link connecting ISL interface circuitry disposed at two switches required translation of TR frames to Ethernet format. The present invention is directed to an encapsulation technique for transporting TR frames in their native TR formats over an ISL link.
The invention relates to a technique for efficiently transporting token ring (TR) frames over trunks interconnecting switches of a distributed TR bridge. The TR bridge is characterized by a logical switch fabric that is distributed among the interconnected switches by the trunks, which are preferably interswitch link (ISL) trunks. Each switch includes a Bridge Relay Function (BRF) coupled to a plurality of Concentrator Relay Functions (CRFs) having a plurality of ports for receiving TR frames over TR segments. The BRF and CRF of the distributed TR bridge operate according to a 2-tier switching model wherein each CRF and BRF is assigned an individual virtual local area network (VLAN) identifier.
According to the invention, the technique encapsulates the TR frames in a TR-ISL protocol format that accomodates differences in formats of various TR frames. The novel s protocol comprises a TR-ISL header having a destination VLAN field, a source VLAN field, a destination route descriptor (RD) field, a source RD field, an F field and an E size field. The contents of the E size field specify the extent of padding (if necessary) for the encapsulated TR frame. The F field contains an FCS not present indicator, whereas the contents of the source and destination RD fields are used for forwarding decision operations, as in the case of a Specifically Routed Frame, an All Routes Explorer frame or a Spanning Tree Explorer frame. If there are no RD contents in these fields, as in the case of a Non-Source Route frame, the forwarding decision is based on a destination medium access control address.
In the illustrative embodiment, the 2-tier switching arrangement is further governed by special inbound frame processing and forwarding rules required to select target ports for the frames. Specifically, parsing operations are performed on an incoming frame at a switch to compute the contents of the destination and source VLAN fields of the TR-ISL header, along with the source and destination RD fields. The computed information is carried with the incoming frame and used by interface circuitry of each switch to access a modified forwarding table when rendering a forwarding decision for the frame. The novel TR-ISL protocol format accomodates the computed information needed to comport with the 2-tier switching model of the distributed TR bridge and the special processing/forwarding rules.
Advantageously, the invention obviates the need to translate TR frames to an Ethernet format (and vice versa) when those frames are forwarded over a trunk link, such as ISL. This is particularly useful in multi-path networks wherein translation is often not an option since it prevents use of alternate paths and limits performance in such networks. In addition, the invention facilitates reconfiguration of a network of switches by adding ISL links and switches without requiring changes to ring numbers in the network and without adding additional hops in the routing information field of the TR frames.